home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / glibc108.zip / glibc108 / hurd / hurdmalloc.c < prev    next >
C/C++ Source or Header  |  1994-06-03  |  9KB  |  384 lines
  1. #include <stdlib.h>
  2. #include "hurdmalloc.h"        /* XXX see that file */
  3.  
  4. #include <gnu-stabs.h>
  5. text_set_element (_hurd_fork_prepare_hook, malloc_fork_prepare);
  6. text_set_element (_hurd_fork_parent_hook, malloc_fork_parent);
  7. text_set_element (_hurd_fork_child_hook, malloc_fork_child);
  8. text_set_element (_hurd_preinit_hook, malloc_init);
  9.  
  10.  
  11. /* 
  12.  * Mach Operating System
  13.  * Copyright (c) 1991,1990,1989 Carnegie Mellon University
  14.  * All Rights Reserved.
  15.  * 
  16.  * Permission to use, copy, modify and distribute this software and its
  17.  * documentation is hereby granted, provided that both the copyright
  18.  * notice and this permission notice appear in all copies of the
  19.  * software, derivative works or modified versions, and any portions
  20.  * thereof, and that both notices appear in supporting documentation.
  21.  * 
  22.  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  23.  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
  24.  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  25.  * 
  26.  * Carnegie Mellon requests users of this software to return to
  27.  * 
  28.  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  29.  *  School of Computer Science
  30.  *  Carnegie Mellon University
  31.  *  Pittsburgh PA 15213-3890
  32.  * 
  33.  * any improvements or extensions that they make and grant Carnegie Mellon
  34.  * the rights to redistribute these changes.
  35.  */
  36. /*
  37.  * HISTORY
  38.  * $Log:    malloc.c,v $
  39.  * Revision 2.7  91/05/14  17:57:34  mrt
  40.  *     Correcting copyright
  41.  * 
  42.  * Revision 2.6  91/02/14  14:20:26  mrt
  43.  *     Added new Mach copyright
  44.  *     [91/02/13  12:41:21  mrt]
  45.  * 
  46.  * Revision 2.5  90/11/05  14:37:33  rpd
  47.  *     Added malloc_fork* code.
  48.  *     [90/11/02            rwd]
  49.  * 
  50.  *     Add spin_lock_t.
  51.  *     [90/10/31            rwd]
  52.  * 
  53.  * Revision 2.4  90/08/07  14:31:28  rpd
  54.  *     Removed RCS keyword nonsense.
  55.  * 
  56.  * Revision 2.3  90/06/02  15:14:00  rpd
  57.  *     Converted to new IPC.
  58.  *     [90/03/20  20:56:57  rpd]
  59.  * 
  60.  * Revision 2.2  89/12/08  19:53:59  rwd
  61.  *     Removed conditionals.
  62.  *     [89/10/23            rwd]
  63.  * 
  64.  * Revision 2.1  89/08/03  17:09:46  rwd
  65.  * Created.
  66.  * 
  67.  *
  68.  * 13-Sep-88  Eric Cooper (ecc) at Carnegie Mellon University
  69.  *    Changed realloc() to copy min(old size, new size) bytes.
  70.  *    Bug found by Mike Kupfer at Olivetti.
  71.  */
  72. /*
  73.  *     File:     malloc.c
  74.  *    Author: Eric Cooper, Carnegie Mellon University
  75.  *    Date:    July, 1988
  76.  *
  77.  *     Memory allocator for use with multiple threads.
  78.  */
  79.  
  80.  
  81. #include <cthreads.h>
  82. #include "cthread_internals.h"
  83.  
  84. /*
  85.  * C library imports:
  86.  */
  87. extern bcopy();
  88.  
  89. /*
  90.  * Structure of memory block header.
  91.  * When free, next points to next block on free list.
  92.  * When allocated, fl points to free list.
  93.  * Size of header is 4 bytes, so minimum usable block size is 8 bytes.
  94.  */
  95. typedef union header {
  96.     union header *next;
  97.     struct free_list *fl;
  98. } *header_t;
  99.  
  100. #define MIN_SIZE    8    /* minimum block size */
  101.  
  102. typedef struct free_list {
  103.     spin_lock_t lock;    /* spin lock for mutual exclusion */
  104.     header_t head;        /* head of free list for this size */
  105. #ifdef    DEBUG
  106.     int in_use;        /* # mallocs - # frees */
  107. #endif    DEBUG
  108. } *free_list_t;
  109.  
  110. /*
  111.  * Free list with index i contains blocks of size 2^(i+3) including header.
  112.  * Smallest block size is 8, with 4 bytes available to user.
  113.  * Size argument to malloc is a signed integer for sanity checking,
  114.  * so largest block size is 2^31.
  115.  */
  116. #define NBUCKETS    29
  117.  
  118. static struct free_list malloc_free_list[NBUCKETS];
  119.  
  120. /* Initialization just sets everything to zero, but might be necessary on a
  121.    machine where spin_lock_init does otherwise, and is necessary when
  122.    running an executable that was written by something like Emacs's unexec.
  123.    It preserves the values of data variables like malloc_free_list, but
  124.    does not save the vm_allocate'd space allocated by this malloc.  */
  125.  
  126. static void
  127. malloc_init (void)
  128. {
  129.   int i;
  130.   for (i = 0; i < NBUCKETS; ++i)
  131.     {
  132.       spin_lock_init (&malloc_free_list[i].lock);
  133.       malloc_free_list[i].head = NULL;
  134. #ifdef DEBUG
  135.       malloc_free_list[i].in_use = 0;
  136. #endif
  137.     }
  138. }
  139.  
  140. static void
  141. more_memory(size, fl)
  142.     int size;
  143.     register free_list_t fl;
  144. {
  145.     register int amount;
  146.     register int n;
  147.     vm_address_t where;
  148.     register header_t h;
  149.     kern_return_t r;
  150.  
  151.     if (size <= vm_page_size) {
  152.         amount = vm_page_size;
  153.         n = vm_page_size / size;
  154.         /*
  155.          * We lose vm_page_size - n*size bytes here.  */
  156.     } else {
  157.         amount = size;
  158.         n = 1;
  159.     }
  160.     MACH_CALL(vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE), r);
  161.     h = (header_t) where;
  162.     do {
  163.       h->next = fl->head;
  164.       fl->head = h;
  165.       h = (header_t) ((char *) h + size);
  166.     } while (--n != 0);
  167. }
  168.  
  169. /* Declaration changed to standard one for GNU.  */
  170. void *
  171. malloc(size)
  172.     register size_t size;
  173. {
  174.     register int i, n;
  175.     register free_list_t fl;
  176.     register header_t h;
  177.  
  178.     if ((int) size < 0)        /* sanity check */
  179.         return 0;
  180.     size += sizeof(union header);
  181.     /*
  182.      * Find smallest power-of-two block size
  183.      * big enough to hold requested size plus header.
  184.      */
  185.     i = 0;
  186.     n = MIN_SIZE;
  187.     while (n < size) {
  188.         i += 1;
  189.         n <<= 1;
  190.     }
  191.     ASSERT(i < NBUCKETS);
  192.     fl = &malloc_free_list[i];
  193.     spin_lock(&fl->lock);
  194.     h = fl->head;
  195.     if (h == 0) {
  196.         /*
  197.          * Free list is empty;
  198.          * allocate more blocks.
  199.          */
  200.         more_memory(n, fl);
  201.         h = fl->head;
  202.         if (h == 0) {
  203.             /*
  204.              * Allocation failed.
  205.              */
  206.             spin_unlock(&fl->lock);
  207.             return 0;
  208.         }
  209.     }
  210.     /*
  211.      * Pop block from free list.
  212.      */
  213.     fl->head = h->next;
  214. #ifdef    DEBUG
  215.     fl->in_use += 1;
  216. #endif    DEBUG
  217.     spin_unlock(&fl->lock);
  218.     /*
  219.      * Store free list pointer in block header
  220.      * so we can figure out where it goes
  221.      * at free() time.
  222.      */
  223.     h->fl = fl;
  224.     /*
  225.      * Return pointer past the block header.
  226.      */
  227.     return ((char *) h) + sizeof(union header);
  228. }
  229.  
  230. /* Declaration changed to standard one for GNU.  */
  231. void
  232. free(base)
  233.     void *base;
  234. {
  235.     register header_t h;
  236.     register free_list_t fl;
  237.     register int i;
  238.  
  239.     if (base == 0)
  240.         return;
  241.     /*
  242.      * Find free list for block.
  243.      */
  244.     h = (header_t) (base - sizeof(union header));
  245.     fl = h->fl;
  246.     i = fl - malloc_free_list;
  247.     /*
  248.      * Sanity checks.
  249.      */
  250.     if (i < 0 || i >= NBUCKETS) {
  251.         ASSERT(0 <= i && i < NBUCKETS);
  252.         return;
  253.     }
  254.     if (fl != &malloc_free_list[i]) {
  255.         ASSERT(fl == &malloc_free_list[i]);
  256.         return;
  257.     }
  258.     /*
  259.      * Push block on free list.
  260.      */
  261.     spin_lock(&fl->lock);
  262.     h->next = fl->head;
  263.     fl->head = h;
  264. #ifdef    DEBUG
  265.     fl->in_use -= 1;
  266. #endif    DEBUG
  267.     spin_unlock(&fl->lock);
  268.     return;
  269. }
  270.  
  271. /* Declaration changed to standard one for GNU.  */
  272. void *
  273. realloc(old_base, new_size)
  274.         void *old_base;
  275.         size_t new_size;
  276. {
  277.     register header_t h;
  278.     register free_list_t fl;
  279.     register int i;
  280.     unsigned int old_size;
  281.     char *new_base;
  282.  
  283.     if (old_base == 0)
  284.       return malloc (new_size);
  285.  
  286.     /*
  287.      * Find size of old block.
  288.      */
  289.     h = (header_t) (old_base - sizeof(union header));
  290.     fl = h->fl;
  291.     i = fl - malloc_free_list;
  292.     /*
  293.      * Sanity checks.
  294.      */
  295.     if (i < 0 || i >= NBUCKETS) {
  296.         ASSERT(0 <= i && i < NBUCKETS);
  297.         return 0;
  298.     }
  299.     if (fl != &malloc_free_list[i]) {
  300.         ASSERT(fl == &malloc_free_list[i]);
  301.         return 0;
  302.     }
  303.     /*
  304.      * Free list with index i contains blocks of size 2^(i+3) including header.
  305.      */
  306.     old_size = (1 << (i+3)) - sizeof(union header);
  307.     /*
  308.      * Allocate new block, copy old bytes, and free old block.
  309.      */
  310.     new_base = malloc(new_size);
  311.     if (new_base != 0)
  312.         bcopy(old_base, new_base, (int) (old_size < new_size ? old_size : new_size));
  313.     free(old_base);
  314.     return new_base;
  315. }
  316.  
  317. #ifdef    DEBUG
  318. void
  319. print_malloc_free_list()
  320. {
  321.       register int i, size;
  322.     register free_list_t fl;
  323.     register int n;
  324.       register header_t h;
  325.     int total_used = 0;
  326.     int total_free = 0;
  327.  
  328.     fprintf(stderr, "      Size     In Use       Free      Total\n");
  329.       for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
  330.          i < NBUCKETS;
  331.          i += 1, size <<= 1, fl += 1) {
  332.         spin_lock(&fl->lock);
  333.         if (fl->in_use != 0 || fl->head != 0) {
  334.             total_used += fl->in_use * size;
  335.             for (n = 0, h = fl->head; h != 0; h = h->next, n += 1)
  336.                 ;
  337.             total_free += n * size;
  338.             fprintf(stderr, "%10d %10d %10d %10d\n",
  339.                 size, fl->in_use, n, fl->in_use + n);
  340.         }
  341.         spin_unlock(&fl->lock);
  342.       }
  343.       fprintf(stderr, " all sizes %10d %10d %10d\n",
  344.         total_used, total_free, total_used + total_free);
  345. }
  346. #endif    DEBUG
  347.  
  348. static void malloc_fork_prepare()
  349. /*
  350.  * Prepare the malloc module for a fork by insuring that no thread is in a
  351.  * malloc critical section.
  352.  */
  353. {
  354.     register int i;
  355.     
  356.     for (i = 0; i < NBUCKETS; i++) {
  357.     spin_lock(&malloc_free_list[i].lock);
  358.     }
  359. }
  360.  
  361. static void malloc_fork_parent()
  362. /*
  363.  * Called in the parent process after a fork() to resume normal operation.
  364.  */
  365. {
  366.     register int i;
  367.  
  368.     for (i = NBUCKETS-1; i >= 0; i--) {
  369.     spin_unlock(&malloc_free_list[i].lock);
  370.     }
  371. }
  372.  
  373. static void malloc_fork_child()
  374. /*
  375.  * Called in the child process after a fork() to resume normal operation.
  376.  */
  377. {
  378.     register int i;
  379.  
  380.     for (i = NBUCKETS-1; i >= 0; i--) {
  381.     spin_unlock(&malloc_free_list[i].lock);
  382.     }
  383. }
  384.